Khi còn trẻ, Trương Phi đã gặp gỡ và kết giao với Lưu Bị và Quan Vũ. Ba người rất thân thiết với nhau, coi nhau như anh em một nhà. Tam quốc chí, Trương Phi truyện viết: "Vũ lớn hơn Phi mấy tuổi, Phi nhận làm anh".

Năm 184, Lưu Bị khởi binh giúp nhà Hán chống quân khởi nghĩa Khăn Vàng, Trương Phi và Quan Vũ theo giúp sức. Nhờ lập công, Lưu Bị được phong làm Huyện úy An Hỷ. Được một thời gian, Lưu Bị bỏ chức Huyện úy vì đánh viên Đốc bưu của triều đình đến hạch sách, Trương Phi theo đi.

Tam Quốc diễn nghĩa kể rằng người đánh viên Đốc bưu là Trương Phi khi ông nóng giận, nhưng trong thực tế chính Lưu Bị làm việc này rồi bỏ ấn từ quan[4].

Trương Phi theo phò tá Lưu Bị đến huyện Hạ Mật[5] làm Huyện thừa (Phó huyện trưởng) theo sự tiến cử của Vô Kỳ Nghị, rồi huyện úy Cao Đường[6].

Ít lâu sau, anh em Lưu Bị, Quan Vũ, Trương Phi giao tranh với quân cướp địa phương bị bại trận, bèn bỏ huyện Cao Đường đến nương nhờ sứ quân Công Tôn Toản ở U châu. Sau đó Trương Phi lại theo Lưu Bị đến Thanh châu giúp Điền Khải chống Viên Thiệu, đóng quân ở Bình Nguyên. Lưu Bị được phong làm Bình Nguyên tướng, bèn cho Quan Vũ, Trương Phi làm Biệt bộ tư mã, thống lĩnh quân đội.

Năm 190, Viên Thiệu tập hợp chư hầu lập liên minh đánh Đổng Trác. Lưu Bị không được mời tham gia.

Tam Quốc Diễn Nghĩa thêu dệt nên chuyện Trương Phi cùng Quan Vũ, Lưu Bị giao chiến với Lã Bố ở cửa ải Hổ Lao là hoàn toàn không có thật.

Năm 193, Phi theo Lưu Bị đi cứu Đào Khiêm ở Từ châu bị Tào Tháo vây đánh, giúp Đào Khiêm giữ được thành Đan Dương. Không lâu sau khi quân Tào rút đi (để về chiếm lại Duyện châu từ tay Lã Bố), Đào Khiêm qua đời, trước khi mất tiến cử Lưu Bị làm Châu mục Từ châu.